package suanfa.sort;

import java.util.Arrays;

public class RadixSort {

    public static void main(String[] args) {
        String[] array={"qd","abc","qwe","hhh","a","cws","ope"};
        System.out.println(Arrays.toString(radixSort(array,3) ));
    }

    private static final int ASCII_RANGE=128;

        public static String[] radixSort(String[] array,int maxLength){
//排序结果数组，用于存储第一次按位排序的临时结果
        String[] sortedArray=new String[array.length];
//从个位开始比较，一直比较到最高位
        for (int i = maxLength-1; i>=0; i--) {
    /*
    计数排序的过程，分成3步：
    1、创建辅助排序的统计数组，并把待排序的字符对号入座，这里为了代码简洁，直接使用ASCII码范围作为数组长度
     */
            int[] count=new int[ASCII_RANGE];

            for (int j = 0; j < array.length; j++) {
                //int index=getCharIndex(array[i],j);
                int index=getCharIndex(array[j],i);
                count[index]++;
            }

            //2、统计数组做变形，后面的元素等于前面的元素之和
            //for (int j = 0; j < count.length; j++) {数组越界
            for (int j = 1; j < count.length; j++) {
                //count[i]=count[i]+count[i-1];数组越界
                count[j]=count[j]+count[j-1];
            }

            //3、倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
            //for (int j = array.length; j>=0 ; j--) {数组越界
            for (int j = array.length-1; j>=0 ; j--) {
//int index=getCharIndex(array[j],j);
                int index=getCharIndex(array[j],i);

                int sortedIndex=count[index]-1;

                sortedArray[sortedIndex]=array[j];

                count[index]--;
            }
//下一轮排序需要以上一轮的排序结果为基础，因此把结果复制给array
            array=sortedArray.clone();
        }
        return array;
    }

    private static int getCharIndex(String str,int k){
        if(str.length()<(k+1)){
            return 0;
        }
        return str.charAt(k);
    }
}



